package com.lc.weekly.lc426.q2;

import java.util.*;


public class Main {

}


class Solution {
    public int getLargestOutlier(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        Map<Integer, List<Integer>> mp = new HashMap<>();
        for (int i = 0; i < n; i ++) {
        	int num = nums[i];
        	List<Integer> list = mp.getOrDefault(num, new ArrayList<Integer>());
        	list.add(i);
            mp.put(num, list);
        }
        
   
        for (int i = n - 1; i >= 0; i--) {
            int remainingSum = totalSum - nums[i];
            
            if (remainingSum % 2 == 0 && mp.containsKey(remainingSum/2)) {
            	List<Integer> list = mp.get(remainingSum/2);
            	if (list.size() == 1 && list.get(0) == i) {
            		continue;
            	}
            	return nums[i];
            }
        }
        return -1;
    }
}








